#ifndef __BITREE_H__
#define __BITREE_H__

#include<stdio.h>
#include<stdlib.h>


#define MAX(a,b) ((a)>(b)?(a):(b))

//假设二叉树中的用户数据是int
typedef int Datatype;
//二叉树的节点类型
typedef struct node 
{
    Datatype data; //数据域,保存节点本身的数据
    struct node *lchild;    //指针域;
    struct node *rchild;    //指针域;
    int h;                  //当前节点的高度,以此节点为根节点的二叉树的高度,空树的高度为0
}BiTNode;




//函数声明
/*
insertNode:往一棵二叉排序树中加入一个元素,使得二叉树任然具有排序性
@root:指针,你要把元素加入到哪一棵树
@x:你要加入的元素的值
返回值:
返回加入元素后的二叉树的根节点的地址
*/

//递归插入代码
BiTNode *insertNode2(BiTNode *root,Datatype x);


/*
pre_order:以先序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/  
void pre_order(BiTNode *t);

/*
mid_order:以中序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/  
void mid_order(BiTNode *t);

/*
last_order:以后序遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/  
void last_order(BiTNode *t);

//返回以t为根节点的二叉树的高度、
int H(BiTNode *t);

/*
level_order:以层次遍历的方法访问t指向的二叉树
@t:指针,指向你要遍历的二叉树的根节点
返回值:无
*/  
void level_order2(BiTNode *t);


//打印二叉树的4种遍历方式
void orderTree(BiTNode *);

/*
SingleRotateWithRight:对以k为根节点的二叉树进行单向右旋平衡处理
@k:指针,指向你要处理的不平衡子树的根节点
返回值:
    返回旋转之后的子树的根节点的指针
*/
BiTNode * SingleRotateWithRight(BiTNode *k);

/*
SingleRotateWithLeft:对以k为根节点的二叉树进行单向左旋平衡处理
@k:指针,指向你要处理的不平衡子树的根节点
返回值:
    返回旋转之后的子树的根节点的指针
*/
BiTNode * SingleRotateWithLeft(BiTNode *k);

/*
DoubleRotateLeftRight:对以k为根节点的二叉树进行双向旋转(先左后右)平衡处理
@k:指针,指向你要处理的不平衡子树的根节点
返回值:
    返回旋转之后的子树的根节点的指针
*/
BiTNode * DoubleRotateLeftRight(BiTNode *k);

/*
DoubleRotateRightLeft:对以k为根节点的二叉树进行双向旋转(先右后左)平衡处理
@k:指针,指向你要处理的不平衡子树的根节点
返回值:
    返回旋转之后的子树的根节点的指针
*/
BiTNode * DoubleRotateRightLeft(BiTNode *k);

#endif 